#include "graph.h"
#include "func_generales.h"

Path* walk(Graph * G, int current_stainer_node, list<int>* opgr2_nodes_non_analized);
int AddEdgesBetweenTerminalsAndEdgesBetweenNodesWithGradeMoreTwo(Graph *  G,list<Path*>* key_path_descomposition);

list<Path*> * Graph::KeyPathDescomposition() {
	int current_stainer_node;
	Path* current_key_path;
	list<int>* opgr2_nodes_non_analized = new list<int>();  // Defino: nodos de stainer de grado 2
	list<Path*>* key_path_descomposition = new list<Path*>();

	// Inicializo con todos los nodos de Steiner de grado igual a dos
	for (int i = 0; i < sizeG; i++)
		if (actived_node[i] && !IsTerminal(i) && GetNodeGrade(i) == 2)
			opgr2_nodes_non_analized->push_back(i);

	while (!opgr2_nodes_non_analized->empty()) {

		current_stainer_node = SelectRandom(opgr2_nodes_non_analized);

		// Comienzo una caminata desde este nodo hasta que no pueda avanzar mas
		current_key_path = walk(this, current_stainer_node, opgr2_nodes_non_analized);
		if (current_key_path->Length() < 2) {
			delete current_key_path;
		}
		else {
			key_path_descomposition->push_front(current_key_path);
		}
	}

	//Agrego todas las aristas directas entre dos nodos terminales y ademas
	//agrego todas las aristas directas entre dos nodos (cualesquiera) ambos con grado mayor a dos
	AddEdgesBetweenTerminalsAndEdgesBetweenNodesWithGradeMoreTwo(this, key_path_descomposition);

	opgr2_nodes_non_analized->clear();
	delete opgr2_nodes_non_analized;

	return key_path_descomposition;
}

// Alarga el key path hacia sus dos extremos
//
Path* walk(Graph * G, int opgr2_node, list<int>* opgr2_nodes_non_analized) {

	list<int> * neighbords;
	int neighbord_dir_a, neighbord_dir_b;
	int node_ant;
	int node_aux;
	Path* key_path = new Path();
	key_path->path->push_front(opgr2_node);

	neighbords = G->GetNeighbors(opgr2_node);

	neighbord_dir_a = neighbords->front(); // elijo insertar al frente (abajo)
	neighbord_dir_b = neighbords->back(); // elijo insertar al final (abajo)

	DeleteListInt(neighbords);

	// Me muevo en direccion A, elijo insertar al frente
	node_ant = opgr2_node;
	while(!opgr2_nodes_non_analized->empty() && !G->IsTerminal(neighbord_dir_a) && ((neighbords = G->GetNeighbors(neighbord_dir_a))->size() == 2)) {
		key_path->path->push_front(neighbord_dir_a);

		opgr2_nodes_non_analized->remove(neighbord_dir_a);
		//cout << "SizeA : " << opgr2_nodes_non_analized->size() << endl;
		node_aux = neighbord_dir_a;
		neighbord_dir_a = (neighbords->front() != node_ant ? neighbords->front() : neighbords->back());
		node_ant = node_aux;

		DeleteListInt(neighbords);
	}
	if(G->IsTerminal(neighbord_dir_a) || G->GetNodeGrade(neighbord_dir_a) > 2)  key_path->path->push_front(neighbord_dir_a);

	//cout << "////////////////////"<< endl;
	//PrintPath(key_path);
	//cout << "////////////////////"<< endl;

	DeleteListInt(neighbords);

	// Me muevo en direccion B, elijo insertar la final
	node_ant = opgr2_node;
	while(!opgr2_nodes_non_analized->empty() && !G->IsTerminal(neighbord_dir_b) && ((neighbords = G->GetNeighbors(neighbord_dir_b))->size() == 2)) {
		key_path->path->push_back(neighbord_dir_b);

		opgr2_nodes_non_analized->remove(neighbord_dir_b);
		//cout << "SizeB : " << opgr2_nodes_non_analized->size() << endl;
		node_aux = neighbord_dir_b;
		neighbord_dir_b = (neighbords->front() != node_ant ? neighbords->front() : neighbords->back());
		node_ant = node_aux;

		DeleteListInt(neighbords);
	}
	if(G->IsTerminal(neighbord_dir_b) || G->GetNodeGrade(neighbord_dir_b) > 2) key_path->path->push_back(neighbord_dir_b);

	DeleteListInt(neighbords);

	return key_path;
}

int AddEdgesBetweenTerminalsAndEdgesBetweenNodesWithGradeMoreTwo(Graph *  G, list<Path*>* key_path_descomposition) {

	for(int i=0; i<G->sizeG; i++)
		if (G->actived_node[i]) {
			for(int j=i; j<G->sizeG; j++)
				if(G->actived_node[j] && G->E[i][j]) {
					if( (G->IsTerminal(i) && G->IsTerminal(j)) || (G->GetNodeGrade(i) > 2 && G->GetNodeGrade(j) > 2) ) {
						Path* key_path = new Path();
						key_path->path->push_front(i);
						key_path->path->push_front(j);

						key_path_descomposition->push_front(key_path);
					}
 				}

		}

	return 0;
}